/* *************************************************** */
/* * Optimal Hospital Junction Calculator - Parallel * */
/* * Authors:                                        * */
/* *  André Bannwart Perina      7152757             * */
/* *  Rodrigo de Freitas Pereira 7573472             * */
/* *  Thaís Emanuele dos Santos  6453087             * */
/* *************************************************** */

#include <limits.h>
#include <omp.h>
#include <stdio.h>
#include <stdlib.h>

#include "../include/set.h"

/* Define number of threads to be created */
#define NUM_THREADS 8

/* Uncomment below to turn the dijkstra subroutine parallel (dynamic) */
#define DIJKSTRA_PARALLEL
/* Uncomment below to turn the max/min subroutine parallel */
#define MAXMIN_PARALLEL

/* Modified Dijkstra's Algorithm for finding shortest path between source and dest - it returns only the distance */
int dijkstra_dist_only(unsigned int **adj, unsigned int n, unsigned int source, unsigned int dest, unsigned int nonAdjVal) {
	unsigned int i, dist[n];
	set_t *set;

	/* Create set */
	set_create(&set, n);

	/* Set source-to-source distance as 0 */
	dist[source] = 0;

	/* Set all remaining distances to infinity */
	for(i = 0; i < n; i++) {
		if(i != source)
			dist[i] = nonAdjVal;

		/* Insert node on set */
		set_insert(&set, i);
	}

	/* While set is not empty */
	while(set_cardinality(set)) {
		unsigned int elem, minDist = nonAdjVal, alt;

		/* For each node */
		for(i = 0; i < n; i++) {
			/* If set contains node i and its distance is lesser than current minimal distance */
			if(set_contains(set, i) && dist[i] < minDist) {
				/* Save current node as the current minimal distance */
				minDist = dist[i];
				elem = i;
			}
		}
		/* If picked node is destination, finish algorithm */
		if(elem == dest)
			break;

		/* Remove node from set */
		set_remove(&set, elem);

		/* For each node */
		for(i = 0; i < n; i++) {
			/* If node is adjacent to previously picked node */
			if(adj[i][elem] != nonAdjVal) {
				/* Sum this distance to previously picked node distance */
				alt = dist[elem] + adj[i][elem];

				/* If this last calculated distance is lesser than original distance, swap */
				if(alt < dist[i])
					dist[i] = alt;
			}
		}
	}

	/* Destroy set */
	set_destroy(&set);

	/* Return smallest distance */
	return dist[dest];
}

int main(void) {
	unsigned int n, m, **adj, **dist, i, j, *maxVec, min;

	/* Set number of threads */
	omp_set_num_threads(NUM_THREADS);

	/* Read number of nodes and number of edges */
	scanf("%d", &n);
	scanf("%d", &m);
	getchar();

	/* Allocate adjacency matrix and smallest distance matrix */
	adj = malloc(n*sizeof(unsigned int *));
	dist = malloc(n*sizeof(unsigned int *));

	for(i = 0; i < n; i++) {
		adj[i] = malloc(n*sizeof(unsigned int));
		dist[i] = calloc(n, sizeof(unsigned int));

		/* Set the whole graph as disconnected (initialisation) */
		for(j = 0; j < n; j++)
			adj[i][j] = UINT_MAX;
	}

	/* Start adding edges to adjacency matrix */
	for(i = 0; i < m; i++) {
		int u, v, w;

		scanf("%d", &u);
		scanf("%d", &v);
		scanf("%d", &w);
		getchar();

		adj[u-1][v-1] = adj[v-1][u-1] = w;
	}

	/* Calculate smallest distance for each pair of nodes from the graph */
#ifdef DIJKSTRA_PARALLEL
#pragma omp parallel for schedule(dynamic)
#endif
	for(i = 0; i < n; i++)
#ifdef DIJKSTRA_PARALLEL
#pragma omp parallel for schedule(dynamic)
#endif
		for(j = i; j < n; j++)
			if(i != j)
				dist[i][j] = dist[j][i] = dijkstra_dist_only(adj, n, i, j, UINT_MAX);

	/* Initialise vector of maxima */
	maxVec = calloc(n, sizeof(unsigned int));
	/* Initialise minimum variable */
	min = UINT_MAX;

/* Parallel version */
#ifdef MAXMIN_PARALLEL
	unsigned int maxAux;

	/* For each line, get its largest distance */
	for(i = 0; i < n; i++) {
		maxAux = 0;

/* Parallel max reduction */
#pragma omp parallel for reduction(max : maxAux)
		for(j = 0; j < n; j++) {
			if(dist[i][j] > maxAux)
				maxAux = dist[i][j];
		}

		maxVec[i] = maxAux;
	}

	/* Get smallest value from vector of maxima */
/* Parallel min reduction */
#pragma omp parallel for reduction(min : min)
	for(i = 0; i < n; i++) {
		if(maxVec[i] < min)
			min = maxVec[i];
	}

/* Sequential Version */
#else
	/* For each line, get its largest distance */
	for(i = 0; i < n; i++) {
		for(j = 0; j < n; j++) {
			if(dist[i][j] > maxVec[i])
				maxVec[i] = dist[i][j];
		}
	}

	/* Get smallest value from vector of maxima */
	for(i = 0; i < n; i++) {
		if(maxVec[i] < min)
			min = maxVec[i];
	}
#endif

	/* Print the smallest among the biggest distances */
	printf("%d\n", min);

	/* Free everything */
	for(i = 0; i < n; i++) {
		free(adj[i]);
		free(dist[i]);
	}
	free(adj);
	free(dist);
	free(maxVec);

	return 0;
}